/**
23. 合并K个升序链表
	给你一个链表数组，每个链表都已经按升序排列。
	请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */

package main


// 暴力法：顺序合并
func mergeKLists1(lists []*ListNode) *ListNode {
	if lists==nil || len(lists)==0 {
		return nil
	}
	res:=&ListNode{0,nil}
	res.Next = lists[0]
	for i:=1;i<len(lists);i++ {
		res.Next=mergeTwoLists(res.Next, lists[i])
	}
	return res.Next
}

// 递归
func mergeKLists2(lists []*ListNode) *ListNode {
	if lists==nil || len(lists) ==0 {
		return nil
	}

	if len(lists) == 1{
		return lists[0]
	}
	lists[1]= mergeTwoLists(lists[0], lists[1])
	return mergeKLists(lists[1:])
}

// 分治法：两两合并
func mergeKLists(lists []*ListNode) *ListNode {
	if lists==nil || len(lists)==0 {
		return nil
	}
	return mergeLists(lists, 0, len(lists)-1)
}


// 分治法
func mergeLists(lists []*ListNode, start int, end int) *ListNode {
	if start>end {
		return nil
	}

	if start==end {
		return lists[start]
	}

	mid:= (start+end)/2

	return mergeTwoLists(mergeLists(lists, start, mid) , mergeLists(lists,mid+1, end))
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	// 保护节点
	protect_node := &ListNode{0,nil}
	temp := protect_node
	// 遍历两个链表，比较两个链表的节点的大小
	for l1!=nil && l2!=nil {
		if l1.Val<l2.Val {
			temp.Next = l1
			l1 = l1.Next
		}else {
			temp.Next = l2
			l2 = l2.Next
		}
		temp=temp.Next
	}
	// 判断有没有不为空的链表
	if l1!=nil {
		temp.Next = l1
	}
	if l2 !=nil {
		temp.Next = l2
	}
	return protect_node.Next
}

type ListNode struct {
	Val int
	Next *ListNode
}